In the field of digital communications, forward error correction (FEC) through the application of an error correcting code (ECC) is the technique of encoding messages to add redundancy in order to mitigate the uncertainty introduced by a noisy communication channel, allowing transmission errors to be reduced by a decoder. Generally, an ECC is a technique for converting a sequence of data symbols (representing a message) into a more redundant sequence of code symbols that are transmitted over a noisy channel. A decoder is a system or a method for recovering an estimate of the data symbols from the noisy output of the channel.
A particular family of ECCs called polar codes was introduced by Arikan in 2009, which provides an explicit code construction technique for binary input channels along with a decoder that provably converges toward optimal coding efficiency (i.e., achieving the channel capacity) in the asymptotic of coding over larger blocks of data. The polar codes, as proposed by Arikan, encode a message, represented as a sequence of k data binary symbols (“bits”), into a sequence of n code bits, where n is a power of two in general and larger than k. Specifically, the encoding procedure first writes the k data bits into the vector u:=(u0, . . . , un−1) at the k locations specified by a data index set I⊂{0, . . . , n−1} with cardinality |I|=k, while the remaining n−k locations are set to arbitrary, but known, fixed values.
Then, the n coded bits, denoted by the vector c:=(c0, . . . , cn−1), are determined by the formula c=uBF⊗m, where the matrix multiplications are carried out over the binary field (i.e., modulo-2 arithmetic), B denotes the n×n bit-reversal permutation matrix, and F⊗m in is the m-th Kronecker power of the matrix
      F    :=          [                                    1                                0                                                1                                1                              ]        ,and m:=log2 n is the polarization stage. A polar code is fully specified by the data index set I and the parameters n and k. Thus, the key to constructing a polar code is choosing a data index set I (equivalently, its complementary set, frozen bit location) suitable for the noisy channel.
The successive cancellation (SC) decoder provided by Arikan helps explaining the specifics of the polar code construction technique. The SC decoder takes as input the noisy output of the channel denoted by y:=(y0, . . . , yn−1), where each yi is a noisy observation of the corresponding code bit ci. The SC decoder proceeds sequentially over the bits, from index 0 to n−1, where for each index i∈{0, . . . , (n−1)}, an estimate ûi for bit ui is made as follows: if i∉I (i.e., frozen bit location), then ûi is set to the known, fixed value of ui, otherwise, when i∈I, ûi is set to the most likely value for ui given the channel outputs y and assuming that the previous estimates (û0, . . . , ûi−1) are correct. Sampling these estimates at the indices i∈I gives the estimate for the data bits. Each estimate ûi is made with respect to the conditional distribution P(y, u0, . . . , ui−1|ui), which follows from the polar code structure and underlying channel statistics, and can also be thought to represent a pseudo-channel for the bit ui. With the aim of maximizing the accuracy of the estimates ûi, the data index set I should be chosen to select the k most reliable pseudo-channels.
Polar codes can also be systematically encoded, which is a key property to enable their application in certain concatenated codes. The systematic encoding procedure for polar codes produces a valid codeword such that the data bits appear directly in the codeword at the locations specified by the index J, which denotes the bit-reversal permutation of the locations in I. The system encoding procedure writes the k data bits into a vector u at the locations in J, while the other locations are set to zero, and then applies the polar encoding procedure twice, while setting the frozen bit locations (i.e., the locations not in I) to zero on the intermediate result between the encodings. This procedure is equivalent to applying the formula c=ϕI(uBF⊗m)BF⊗m, where ϕI(·) denotes setting the bits at the locations not in I equal to zero. The codeword c that results from this procedure contains the data bits written at the locations in J, while the remaining locations not in J contain bits called the parity bits. In some situations, it may be convenient to rearrange the codeword c by a permutation that places the k data bit locations (specified by the index set J) first, followed by the n−k parity locations (specified by the complement of the index set J). With such a permutation, the encoding procedure results in the vector of k data bits appended with the n−k parity bits computed by the systematic polar encoding procedure.
While the SC decoder achieves capacity in the asymptotic of large code length n, as proven by Arikan, its practical error correction performance for shorter code lengths n can be improved. A list-decoding improvement of the SC decoder (SCL) was proposed by Tal and Vardy in 2015. The SCL decoder proceeds similarly to the SC decoder, except that for each data bit index i∈I, the decoder branches to consider both possible estimates, ûi=0 and ûi=1, and their subsequent decoding paths. If left unchecked, this branching would double the number of paths each at i∈I, leading to 2k paths, corresponding to all 2k possible data bit sequences, being considered. Since handling an exponentially increasing number of paths is impractical, the list-decoding approach culls the number of paths to a fixed-size list of the most likely partial paths after the doubling of paths from the branching for each i∈I. This procedure produces a fixed-size list of full decoding paths to consider, from which the most likely full path is selected to produce the estimated data sequence.
While the ultimate objective may be to make a hard-decision for the estimate of the original data symbols, it may also be useful to have a decoder that outputs soft-decision information (“soft-outputs”) that represent estimated beliefs or likelihoods about the data symbols and/or code symbols. Soft-output decoders are useful components in the construction of more complex receivers, e.g., for decoding concatenated ECCs, which are formed from multiple component ECCs that are combined into a higher performance code. Another example is a system employing iterative equalization and decoding.
Both the SC and SCL decoders provide only hard-decision outputs for polar encoded codewords. Some methods, e.g., soft cancelation (SCAN) decoding and belief propagation (BP) decoding, provide soft-decision information for the polar encoded codewords. However, those methods require multiple iterations to generate each set of soft-outputs, and, thus, time, memory, and computational power expensive.
Accordingly, there is a need for a system and method for soft-output decoding of a codeword encoded with polar codes.